Distributed Parallel Construction Algorithm for Triadic Concepts
LI Jinhai1,2,3, WANG Kun1,2, CHEN Qiangqiang2,3
1. Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500; 2. Data Science Research Center, Kunming University of Science and Technology, Kunming 650500; 3. Faculty of Science, Kunming University of Science and Technology, Kunming 650500
Abstract：As an extension of formal concept analysis, triadic concept analysis achieves significant results in both theory and applications of high-dimensional data. However, the time complexity of triadic concept generation algorithms, caused by the rapid growth of data volume, typically grows exponentially, presenting significant challenges in practical applications. Therefore, parallel algorithms are crucial. In this paper, a distributed parallel construction algorithm for triadic concepts suitable for large-scale data is proposed. First, the theories of object-attribute triadic concepts and attribute-condition triadic concepts are provided, and it is proved that all triadic concepts can be generated by merging these two types of intermediate concepts. Second, a two-stage aggregation strategy is employed to improve the resilient distributed dataset operator in the Spark framework. Consequently, the data skew problem is effectively solved and the efficiency of the proposed algorithm is significantly improved. Finally, experiments on multiple public datasets indicate that the proposed algorithm performs efficiently in generating triadic concepts for large datasets.
[1] WILLE R.Restructuring Lattice Theory: An Approach Based on Hierarchies of Concepts // IRIVAL I, ed. Ordered Sets. Berlin, Germany: Springer, 1982: 445-470. [2] WANG L, PEI Z, QIN K Y.A Novel Conflict Analysis Model Based on the Formal Concept Analysis. Applied Intelligence, 2023, 53(9): 10699-10714. [3] HU Q, QIN K Y, YANG L.The Updating Methods of Object-Induced Three-Way Concept in Dynamic Formal Contexts. Applied Intelligence, 2023, 53(2): 1826-1841. [4] OUTRATA J, VYCHODIL V.Fast Algorithm for Computing Fixpoints of Galois Connections Induced by Object-Attribute Relational Data. Information Sciences, 2012, 185(1): 114-127. [5] GODIN R, MISSAOUI R, ALAOUI H.Incremental Concept Formation Algorithms Based on Galois (Concept) Lattices. Computational Intelligence, 1995, 11(2): 246-267. [6] LUO C, CAO Q, LI T R, et al. MapReduce Accelerated Attribute Reduction Based on Neighborhood Entropy with Apache Spark. Expert Systems with Applications, 2023, 211. DOI: 10.1016/j.eswa.2022.118554. [7] CHUNDURI R K, CHERUKURI A K.Distributed Three-Way Formal Concept Analysis for Large Formal Contexts. Journal of Parallel and Distributed Computing, 2023, 171: 141-156. [8] LI J H, HUANG C C, XU W H, et al. Cognitive Concept Learning via Granular Computing for Big Data // Proc of the International Conference on Machine Learning and Cybernetics. Washington, USA: IEEE, 2015: 289-294. [9] NIU J J, CHEN D G, LI J H, et al. Fuzzy Rule-Based Classification Method for Incremental Rule Learning. IEEE Transactions on Fuzzy Systems, 2022, 30(9): 3748-3761. [10] NIU J J, CHEN D G, LI J H, et al. A Dynamic Rule-Based Cla-ssification Model via Granular Computing. Information Sciences, 2022, 584: 325-341. [11] LIU Z M, LI J H, ZHANG X, et al. Incremental Incomplete Concept-Cognitive Learning Model: A Stochastic Strategy. IEEE Tran-sactions on Neural Networks and Learning Systems, 2023. DOI: 10.1109/TNNLS.2023.3333537. [12] YAO Y Y.Interpreting Concept Learning in Cognitive Informatics and Granular Computing. IEEE Transactions on Systems, Man, and Cybernetics(Cybernetics), 2009, 39(4): 855-866. [13] WILLE R.The Basic Theorem of Triadic Concept Analysis. Order, 1995, 12(2): 149-158. [14] LEHMANN F, WILLE R.A Triadic Approach to Formal Concept Analysis // Proc of 3rd International Conference on Conceptual Structures: Applications, Implementation and Theory. Berlin, Ger-many: Springer, 1995: 32-43. [15] BIEDERMANN K.An Equational Theory for Trilattices. Algebra Universalis, 1999, 42(4): 253-268. [16] BIEDERMANN K.How Triadic Diagrams Represent Conceptual Struc-tures // Proc of the International Conference on Conceptual Structures. Berlin, Germany: Springer, 1997: 304-317. [17] GANTER B, SERGEI O.Implications in Triadic Formal Contexts // Proc of the 12th International Conference on Conceptual Structures. Berlin, Germany: Springer, 2004: 186-195. [18] KAYTOUE M, KUZNETSOV S O, MACKO J, et al. Biclustering Meets Triadic Concept Analysis. Annals of Mathematics and Artificial Intelligence, 2014, 70(1/2): 55-79. [19] IGNATOV D I, GNATYSHAK D V, KUZNETSOV S O, et al. Triadic Formal Concept Analysis and Triclustering: Searching for Optimal Patterns. Machine Learning, 2015, 101(1/2/3): 271-302. [20] BELOHLAVEK R, OSICKA P.Triadic Concept Lattices of Data with Graded Attributes. International Journal of General Systems, 2012, 41(2): 93-108. [21] BELOHLAVEK R, OSICKA P.Triadic Fuzzy Galois Connections as Ordinary Connections. Fuzzy Sets and Systems, 2014, 249: 83-99. [22] 王霞,张茜,李俊余,等.基于粗糙集的三元概念分析.山东大学学报(理学版), 2017, 52(7): 37-43. (WANG X, ZHANG Q, LI J Y, et al. Triadic Concept Analysis Based on Rough Set Theory. Journal of Shandong University(Natural Science), 2017, 52(7): 37-43.) [23] 汤亚强,范敏,李金海.三元形式概念分析下的认知系统模型及信息粒转化方法.山东大学学报(理学版), 2014, 49(8): 102-106. (TANG Y Q, FAN M, LI J H.Cognitive System Model and Approach to Transformation of Information Granules Under Triadic Formal Concept Analysis. Journal of Shandong University(Natural Science), 2014, 49(8): 102-106.) [24] HAO F, PARK D S, MIN G Y, et al. k-Cliques Mining in Dyna-mic Social Networks Based on Triadic Formal Concept Analysis. Neurocomputing, 2016, 209: 57-66. [25] 李贞,张卓,王黎明.基于三元概念分析的文本分类算法研究.计算机科学, 2017, 44(8): 207-215. (LI Z, ZHANG Z, WANG L M.Research on Text Classification Algorithm Based on Triadic Concept Analysis. Computer Science, 2017, 44(8): 207-215.) [26] 李俊余,朱荣杰,王霞,等.三元概念与形式概念的关系.南京大学学报(自然科学), 2018, 54(4):786-793. (LI J Y, ZHU R J, WANG X, et al. The Relationship Between Triadic Concepts and Formal Concepts. Journal of Nanjing University(Natural Science), 2018, 54(4): 786-793.) [27] 王霞,李俊余,吴伟志.三元概念的布尔矩阵表示方法.计算机科学, 2023, 50(6):109-115. (WANG X, LI J Y, WU W Z.Boolean Matrix Representation of Triadic Concepts. Computer Science, 2023, 50(6): 109-115.) [28] 王霞,江山,李俊余,等.三元概念的一种构造方法.计算机研究与发展, 2019, 56(4): 844-853. (WANG X, JIANG S, LI J Y, et al. A Construction Method of Triadic Concepts. Journal of Computer Research and Development, 2019, 56(4): 844-853.) [29] 祁建军,魏玲.三元背景及概念三元格的简化.计算机科学, 2017, 44(9): 53-57. (QI J J, WEI L.Simplification of Triadic Contexts and Concept Trilattices. Computer Science, 2017, 44(9): 53-57.) [30] KONECNY J, OSICKA P.Triadic Concept Lattices in the Framework of Aggregation Structures. Information Sciences, 2014, 279: 512-527. [31] ANANIAS K H A, MISSAOUI R, RUAS P H B, et al. Triadic Concept Approximation. Information Sciences, 2021, 572: 126-146. [32] WAN Q, LI J H, WEI L.Optimal Granule Combination Selection Based on Multi-granularity Triadic Concept Analysis. Cognitive Computation, 2022, 14(6): 1844-1858. [33] 王霞,全园,李俊余,等.三元概念的增量式构造方法.南京大学学报(自然科学), 2022, 58(1): 19-28. (WANG X, QUAN Y, LI J Y, et al. Incremental Construction Method of Triadic Concepts. Journal of Nanjing University(Natural Science), 2022, 58(1): 19-28.) [34] 李金海,魏玲,张卓,等.概念格理论与方法及其研究展望.模式识别与人工智能, 2020, 33(7): 619-642. (LI J H, WEI L, ZHANG Z, et al. Concept Lattice Theory and Method and Their Research Prospect. Pattern Recognition and Artificial Intelligence, 2020, 33(7): 619-642.) [35] WEI L, QIAN T, WAN Q, et al. A Research Summary about Triadic Concept Analysis. International Journal of Machine Learning and Cybernetics, 2018, 9(4): 699-712. [36] 米允龙,李金海,刘文奇,等.MapReduce框架下的粒概念认知学习系统研究.电子学报, 2018, 46(2): 289-297. (MI Y L, LI J H, LIU W Q, et al. Research on Granular Concept Cognitive Learning System under MapReduce Framework. Acta Electronica Sinica, 2018, 46(2): 289-297.) [37] 蔡勇,陈红梅.MapReduce环境下基于概念分层的概念格并行构造算法.中国科学技术大学学报, 2018, 48(4): 275-283. (CAI Y, CHEN H M.A Parallel Algorithm for Constructing Concept Lattice Based on Hierarchical Concept under MapReduce. Journal of the University of Science and Technology of China, 2018, 48(4): 275-283.) [38] ZAHARIA M, CHOWDHURY M, FRANKLIN M J, et al. Spark: Cluster Computing with Working Sets[J/OL].[2024-09-19]. https://people.csail.mit.edu/matei/papers/2010/hotcloud_spark.pdf. [39] STONE H S. Parallel Processing with the Perfect Shuffle. IEEE Transactions on Computers, 1971, C-20(2): 153-161. [40] 王啸,魏玲,张琴,等.基于待选集的三元概念构造方法.模式识别与人工智能, 2024, 37(7): 584-596. (WANG X, WEI L, ZHANG Q, et al. Triadic Concept Construction Method Based on Candidate Set. Pattern Recognition and Artificial Intelligence, 2024, 37(7): 584-596.)
2024, Vol. 37 
